package com.leet.code.lcof;

public class Code14_2 {

    public static void main(String[] args) {
//        int i = (int) Math.pow(3, 1000);
//        System.out.println((i + "").length());
//        System.out.println("1000000007".length());

//        System.out.println(new Code14_2().pow(3, 2));
//        System.out.println(new Code14_2().pow(3, 5));
        System.out.println(new Code14_2().cuttingRope( 58));
        System.out.println(1549681956% 1000000007);

    }

    public int cuttingRope(int n) {

        if (n <= 3) {
            return n - 1;
        }

        int s = n / 3;
        int y = n % 3;

        int pow;
        if (y == 0) {
            pow = pow(3, s)% 1000000007;
        } else if (y == 1) {
            pow = ((pow(3, s - 1) << 1) % 1000000007) << 1 % 1000000007;
        } else {
            pow = (pow(3, s) << 1) % 1000000007;
        }
        return pow%1000000007;
    }

    public long pow1(int d, int z) {
        if (d == 0) {
            return 0;
        }
        if (z == 0 || d == 1) {
            return 1;
        }
        if (z == 1) {
            return d;
        }

        long pow = d;
        int i = 1;
        int z2 = z >> 1;
        while (i <= z2) {
            pow = pow % 1000000007;
            pow = pow * pow;
            i = i << 1;
        }

        return (pow * pow1(d, z - i)) % 1000000007;
    }

    public int pow(int d, int z) {
        if (d == 0) {
            return 0;
        }
        if (z == 0 || d == 1) {
            return 1;
        }
        if (z == 1) {
            return d;
        }

        int pow = 1;
        for (; z > 0; z--) {
            pow = (pow << 1) % 1000000007 + pow % 1000000007;
            pow = pow % 1000000007;
        }
        return pow;

    }


}
